CS Notes: Abstract Data Types & Asymptotic Trade-offs
The Power of Structural Abstraction (ADTs)
Abstract Data Types (ADTs), such as Queues and Stacks, represent standardized behavioral interfaces completely decoupled from their underlying silicon memory layout. A Stack (LIFO: Last In, First Out) or a Queue (FIFO: First In, First Out) can be physically engineered using either contiguous static arrays or dynamic pointer-backed linked lists.
===================================================================================
STACK (LIFO) VS QUEUE (FIFO) EXECUTION
===================================================================================
STACK (LIFO) QUEUE (FIFO)
┌──────────┐ ┌─────┬─────┬─────┬─────┐
│ Top │ ◄── Push / Pop │ 1 │ 2 │ 3 │ 4 │ ──► Dequeue
├──────────┤ └─────┴─────┴─────┴─────┘
│ Bottom │ ▲
└──────────┘ └─ Enqueue
===================================================================================
Asymptotic Topology & Benchmarking
Algorithmic benchmarking reveals fundamental trade-offs: Static arrays grant O(1) random access but require O(n) shifting for insertion/deletion. Linked lists feature O(1) head insertion but suffer from O(n) linear search sweeps. Hash tables provide near-instantaneous O(1) average lookup latency, whereas balanced BSTs guarantee stable O(log n) logarithmic scaling.
Hash Functions & Collision Resolution
Per the Pigeonhole Principle, if the universe of possible keys exceeds the table capacity N, hash collisions are mathematically inevitable. Collisions are architecturally resolved either via Open Addressing (Linear Probing), which suffers from primary clustering, or Chaining, which converts every table bucket into a linked list head pointer.